package leetcode_day._2021._202107._0110;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/8 15:18
 * 和相同的二元子数组
 * 算法：前缀和  滑动窗口  哈希表
 * 先算出前缀和
 * 用哈希表记录数字出现的次数
 */
public class _08_930 {
    public static void main(String[] args) {
        System.out.println(new _08_930().numSubarraysWithSum(new int[]{1, 0, 1, 0, 1}, 2));
    }

    public int numSubarraysWithSum(int[] nums, int goal) {
        for (int i = 1; i < nums.length; i++) nums[i] += nums[i - 1];
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= goal) {
                int target = nums[i] - goal;
                ans += map.getOrDefault(target, 0);
            }
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        return ans;
    }

}
